/*
 * Tree.h
 *
 *  Created on: Mar 28, 2011
 *      Author: hxu
 *      Tree<root, children>
 */

#ifndef TREE_H_
#define TREE_H_
#include "Network.h"
#include "TreeNode.h"

namespace Cxuh {

template<class Type>
class Tree: public Network<Type>{
	//tree structure, general list
public:
	Tree(int idd);
	virtual ~Tree();
	void Add(Cxuh::Segment<Type>*);
	TreeNode<Type>* First() const {return first;};	// return first
	TreeNode<Type>* Next(TreeNode<Type>* elem) const;	// return elem->next
	void pushBack(TreeNode<Type>*);	// push a tree node to the end of the list (the last child of the root)
	void pushBack(TreeNode<Type>* ref, TreeNode<Type>* elem);	// push elem to the end of ref's list
	template <class TT> friend std::ostream& operator << (std::ostream&, Tree<TT>&);
	//std::ostream& printNode(std::ostream&, TreeNode<Type>* elem); // print info of elem
	int getID() const;
	bool buildTree();	// generate tree structure to be a general list
	//void setHead(TreeNode<Type> *elem); // link the head pointer to the root node
	bool isEmpty();	// whether the tree is empty
	void Merge(TreeNode<Type> *ref, TreeNode<Type> *elem); // merge the children of elem into ref
	bool isRootSet();	// whether the root is set
	void setParent(TreeNode<Type> *elem, TreeNode<Type> *par); // set the parent of elem
	bool equalNode(TreeNode<Type> *elem1, TreeNode<Type> *elem2); // compare the content of two nodes
	void setRoot(TreeNode<Type> *elem);	// set the content of root to be elem
private:
	TreeNode<Type> * first;
	//int depth(TreeNode<Type>*);
	//void remove(TreeNode<Type>*);
	int ndnum; 	// # of nodes excluding SUB and HEA
	int id;	// id of the tree
	bool insTree(TreeNode<Type> *ref, TreeNode<Type> *elem);	// insert elem under ref or its neighbors
	bool rootfound;	// the root of the tree has been found
	TreeNode<Type>* sinks;	// only sinks

};

}

#endif /* TREE_H_ */
